#include <stdio.h>
#include <stdlib.h>
#include "Tree.h"


int TreeInit(Tree* tree) {
	tree->root = malloc(sizeof(TreeNode));
	if (tree->root == NULL) {
		return 1;
	}
	tree->root->data = 0;
	tree->root->firstChild = NULL;
	tree->root->nextSibling = NULL;
	return 0;
}


TreeNode* TreeAppendChild(TreeNode* parent, ElemType elem) {
	TreeNode* newNode = malloc(sizeof(TreeNode));
	if (newNode == NULL) {
		return NULL;
	}
	newNode->data = elem;
	newNode->firstChild = NULL;
	newNode->nextSibling = NULL;
	if (parent->firstChild == NULL) {
		parent->firstChild = newNode;
		return newNode;
	}
	else {
		TreeNode* prevNode = parent->firstChild;
		for (; prevNode->nextSibling != NULL; prevNode = prevNode->nextSibling) {}
		prevNode->nextSibling = newNode;
		return newNode;
	}
}


int TreePrintCore(TreeNode* root, int idx) {
	for (int x = 0; x < idx; x += 1) {
		printf("    ");
	}
	printf("%d\n", root->data);
	for (TreeNode* node = root->firstChild; node != NULL; node = node->nextSibling) {
		TreePrintCore(node, idx + 1);
	}
	return 0;
}


int TreePrint(TreeNode* root) {
	TreePrintCore(root, 0);
	return 0;
}


// **** (1)
// *│** (2)
// *├── (3)
// *└── (4)
int TreePrintBeautyCore(TreeNode* root, int idle[], int idx) {
	if (idx > 0) {
		if (root->nextSibling == NULL) {
			idle[idx-1] = 4;
		}
		else {
			idle[idx-1] = 3;
		}
	}
	for (int x = 0; idle[x] != 0; x += 1) {
		if (idle[x] == 1) {
			printf("    ");
		}
		else if (idle[x] == 2) {
			printf(" │  ");
		}
		else if (idle[x] == 3) {
			printf(" ├──");
		}
		else if (idle[x] == 4) {
			printf(" └──");
		}
	}
	if (idx > 0) {
		if (root->nextSibling == NULL) {
			idle[idx-1] = 1;
		}
		else {
			idle[idx-1] = 2;
		}
	}
	printf("%d\n", root->data);
	for (TreeNode* node = root->firstChild; node != NULL; node = node->nextSibling) {
		TreePrintBeautyCore(node, idle, idx + 1);
	}
	if (idx > 0) {
		idle[idx-1] = 0;
	}
	return 0;
}


int TreePrintBeauty(TreeNode* root) {
	int idle[1000];
	for (int idx = 0; idx < 100; idx += 1) {
		idle[idx] = 0;
	}
	TreePrintBeautyCore(root, idle, 0);
	return 0;
}


int TreeDetailCore(TreeNode* root) {
	printf("%-25p %-15d %-25p %-25p\n",
	       root, root->data, root->firstChild, root->nextSibling);
	for (TreeNode* node = root->firstChild; node != NULL; node = node->nextSibling) {
		TreeDetailCore(node);
	}
	return 0;
}


int TreeDetail(TreeNode* root) {
	printf("%-25s %-15s %-25s %-25s\n",
	       "Node Address", "Data", "First Child", "Next Sibling");
	TreeDetailCore(root);
	return 0;
}


TreeNode* TreeParent(TreeNode* root, TreeNode* child) {
	for (TreeNode* node = root->firstChild; node != NULL; node = node->nextSibling) {
		if (node == child) {
			return root;
		}
		TreeNode* rtn = TreeParent(node, child);
		if (rtn != NULL) {
			return rtn;
		}
	}
	return NULL;
}


int TreeDeleteNodeCore(TreeNode* target) {
	for (TreeNode* node = target->firstChild; node != NULL; ) {
		TreeNode* next = node->nextSibling;
		TreeDeleteNodeCore(node);
		node = next;
	}
	free(target);
	return 0;
}


int TreeDeleteNode(TreeNode* root, TreeNode* target) {
	TreeNode* parent = TreeParent(root, target);
	if (parent == NULL) {
		return 1;
	}
	if (parent->firstChild == target) {
		parent->firstChild = target->nextSibling;
	}
	else {
		TreeNode* prev = parent->firstChild;
		for (; prev->nextSibling != target; prev = prev->nextSibling) {}
		prev->nextSibling = target->nextSibling;
	}
	TreeDeleteNodeCore(target);
	return 0;
}


int TreeAppendNode(TreeNode* parent, TreeNode* node) {
	if (node->nextSibling != NULL) {
		return 1;
	}
	if (parent->firstChild == NULL) {
		parent->firstChild = node;
		return 0;
	}
	else {
		TreeNode* prev = parent->firstChild;
		for (; prev->nextSibling != NULL; prev = prev->nextSibling) {}
		prev->nextSibling = node;
		return 0;
	}
}


int TreeCopyAllChild(TreeNode* des, TreeNode* src) {
	for (TreeNode* node = src->firstChild; node != NULL; node = node->nextSibling) {
		TreeNode* nd = malloc(sizeof(TreeNode));
		nd->data = node->data;
		nd->firstChild = NULL;
		nd->nextSibling = NULL;
		TreeAppendNode(des, nd);
		TreeCopyAllChild(nd, node);
	}
	return 0;
}


TreeNode* TreeClone(TreeNode* root) {
	TreeNode* newRoot = malloc(sizeof(TreeNode));
	newRoot->data = root->data;
	newRoot->firstChild = NULL;
	newRoot->nextSibling = NULL;
	TreeCopyAllChild(newRoot, root);
	return newRoot;
}


int TreeDestory(Tree* tree) {
	TreeDeleteNodeCore(tree->root);
	tree->root = NULL;
	return 0;
}


int main() {
	Tree tree;
	TreeInit(&tree);
	TreeNode* child1 = TreeAppendChild(tree.root, 600);
	TreeNode* child2 = TreeAppendChild(tree.root, 900);
	TreeAppendChild(child1, 650);
	TreeAppendChild(child1, 655);
	TreeAppendChild(child1, 659);
	TreeAppendChild(child2, 960);
	TreeAppendChild(child2, 970);
	TreeAppendChild(child2, 980);
	TreeAppendChild(child2, 985);
	TreeAppendChild(child2, 990);
	TreePrintBeauty(tree.root);
	TreeDetail(tree.root);

	return 0;
}
